package com.xiaoyu.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Queue;
import java.util.Stack;

/**
 * @program: DS_and_A
 * @description:  计算一个字符串表达式的结果
 *
 *  "2*6+3-5*6+2-4" = ?
 *
 *  总体思路:
 *      1.遍历字符串,把数字和操作符入不同的栈
 *      2.在遍历的同时,把所有的乘除法先执行,然后把结果入栈
 *      3.再遍历栈,把所有栈中的元素都依次从左到右执行,即可完成计算
 *
 * @author: YuWenYi
 * @create: 2021-04-26 11:12
 **/


/*
* if (symbolStack.isEmpty()){
        symbolStack.push(exp.charAt(i));   //放入符号栈
    }else {
        //判断当前表达式的优先级是否小于等于栈顶元素优先级
        if (map.get(exp.charAt(i)) < map.get(symbolStack.peek())){
            Integer first = numStack.pop();
            Integer second = numStack.pop();
            Character operate = symbolStack.pop();

            Integer operateNum = operateNum(first, second, operate);
            numStack.push(operateNum);
        }
        symbolStack.push(exp.charAt(i));
    }
*/
public class ComputeString {
    private static HashMap<Character,Integer> map = new HashMap<>();
    static {
        map.put('*',2);  //数字越大,优先级越高
        map.put('/',2);
        map.put('+',1);
        map.put('-',1);
    }

    public static int computeStr(String exp){
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> symbolStack = new Stack<>();

        for (int i = 0; i < exp.length(); i++) {
            if (Character.isDigit(exp.charAt(i))){
                StringBuilder keepNum = new StringBuilder();
                keepNum.append(exp.charAt(i));
                while (true){
                    if (i == exp.length()-1){
                        break;
                    }
                    if (Character.isDigit(exp.charAt(i+1))){
                        keepNum.append(exp.charAt(i+1));
                        i++;
                    }else {
                        break;
                    }
                }
                numStack.push(Integer.parseInt(keepNum.toString()));  //放入数栈

            }else {
                if (!symbolStack.isEmpty()) {
                    //判断当前表达式的优先级是否小于等于栈顶元素优先级
                    if (map.get(exp.charAt(i)) < map.get(symbolStack.peek())) {
                        Integer first = numStack.pop();
                        Integer second = numStack.pop();
                        Character operate = symbolStack.pop();

                        Integer operateNum = operateNum(first, second, operate);
                        numStack.push(operateNum);
                    }
                }
                symbolStack.push(exp.charAt(i));   //放入符号栈
            }
        }

        //由于入栈的顺序,导致原来的出栈计算是反的,所以我需要重新入栈来逆转这个顺序
        Stack<Integer> numStackByRev = new Stack<>();
        Stack<Character> symbolStackByRev = new Stack<>();

        while (!numStack.isEmpty()){
            numStackByRev.push(numStack.pop());
        }
        while (!symbolStack.isEmpty()){
            symbolStackByRev.push(symbolStack.pop());
        }

        while (!symbolStackByRev.isEmpty()){
            Integer first = numStackByRev.pop();
            Integer second = numStackByRev.pop();
            Character operate = symbolStackByRev.pop();

            Integer operateNum = operateNum(second, first, operate);
            numStackByRev.push(operateNum);
        }
        return numStackByRev.peek();
    }

    public static Integer operateNum(int num1,int num2,char operate){
        int resNum = 0;
        switch (operate){
            case '+' : {
                resNum =  num2+num1;
                break;
            }
            case '-' : {
                resNum =  num2-num1;
                break;
            }
            case '*' : {
                resNum =  num2*num1;
                break;
            }
            case '/' :{
                resNum =  num2/num1;
                break;
            } default:{
                throw  new RuntimeException("符号出错了!");
            }
        }
        return resNum;
    }

    public static void main(String[] args) {
        String exp = "3*9+6*3+1-45*1-1+10+5-5-10+6";
        int res = computeStr(exp);
        System.out.println("结果为:-->"+res);
    }
}
